#include <stdlib.h>

#include "algo.h"
#include "algoBase.h"
#include "construct.h"
#include "iterator.h"
#include "Vector.h"

bool vectorIteratorEqualTo(const VectorIterator *_this, const VectorIterator *_vectorIterator) {
	return *_this == *_vectorIterator;
}

bool vectorIteratorNotEqualTo(const VectorIterator *_this, const VectorIterator *_vectorIterator) {
	return *_this != *_vectorIterator;
}

bool vectorIteratorLessThan(const VectorIterator *_this, const VectorIterator *_vectorIterator) {
	return *_this < *_vectorIterator;
}

int *vectorIteratorIndirect(const VectorIterator *_this) {
	return *_this;
}

int *vectorIteratorSubscript(const VectorIterator *_this, ptrdiff_t _n) {
	return &(*_this)[_n];
}

VectorIterator *vectorIteratorIncreasePrefix(VectorIterator *_this) {
	++(*_this);
	return _this;
}

VectorIterator vectorIteratorIncreasePostfix(VectorIterator *_this) {
	VectorIterator temp = *_this;
	vectorIteratorIncreasePrefix(_this);
	return temp;
}

VectorIterator *vectorIteratorDecreasePrefix(VectorIterator *_this) {
	--(*_this);
	return _this;
}

VectorIterator vectorIteratorDecreasePostfix(VectorIterator *_this) {
	VectorIterator temp = *_this;
	vectorIteratorDecreasePrefix(_this);
	return temp;
}

VectorIterator *vectorIteratorAddAssign(VectorIterator *_this, ptrdiff_t _n) {
	(*_this) += _n;
	return _this;
}

VectorIterator vectorIteratorAdd(const VectorIterator *_this, ptrdiff_t _n) {
	VectorIterator temp = *_this;
	return *vectorIteratorAddAssign(&temp, _n);
}

VectorIterator *vectorIteratorSubtractAssign(VectorIterator *_this, ptrdiff_t _n) {
	(*_this) -= _n;
	return _this;
}

VectorIterator vectorIteratorSubtract(const VectorIterator *_this, ptrdiff_t _n) {
	VectorIterator temp = *_this;
	return *vectorIteratorSubtractAssign(&temp, _n);
}

ptrdiff_t vectorIteratorDiff(const VectorIterator *_this, const VectorIterator *_vectorIterator) {
	return *_this - *_vectorIterator;
}

Vector *vectorNew() {
	Vector *vector = (Vector *) malloc(sizeof(Vector));
	vectorConstruct(vector);
	return vector;
}

void vectorDelete(Vector *_this) {
	vectorDestruct(_this);
	free(_this);
}

void vectorConstruct(Vector *_this) {
	_this->begin_ = NULL;
	_this->end_ = NULL;
	_this->endOfStorage_ = NULL;
}

void vectorDestruct(Vector *_this) {
	destructIn(Vector, vectorBegin(_this), vectorEnd(_this));
	free(_this->begin_);
}

int *vectorSubscript(Vector *_this, ptrdiff_t _n) {
	VectorIterator begin = vectorBegin(_this);
	return vectorIteratorSubscript(&begin, _n);
}

const int *vectorSubscriptConst(const Vector *_this, ptrdiff_t _n) {
	VectorConstIterator begin = vectorBeginConst(_this);
	return vectorIteratorSubscript((VectorIterator const *) &begin, _n);
}

VectorIterator vectorBegin(Vector *_this) {
	return _this->begin_;
}

VectorConstIterator vectorBeginConst(const Vector *_this) {
	return _this->begin_;
}

VectorIterator vectorEnd(Vector *_this) {
	return _this->end_;
}

VectorConstIterator vectorEndConst(const Vector *_this) {
	return _this->end_;
}

VectorIterator vectorInsert(Vector *_this, VectorIterator _position, int _value) {
	VectorIterator oldBegin = vectorBegin(_this);
	VectorIterator oldEnd = vectorEnd(_this);
	VectorIterator oldEndOfStorage = _this->endOfStorage_;
	ptrdiff_t diff = vectorIteratorDiff(&_position, &oldBegin);
	if (vectorIteratorNotEqualTo(&oldEnd, &oldEndOfStorage)) {
		VectorIterator newEnd = vectorIteratorAdd(&oldEnd, 1);
		copyBackward(vector, vector, newEnd, _position, oldEnd);
		construct(_position, _value);
		_this->end_ = newEnd;
	}
	else {
		size_t newSize = vectorCapacity(_this);
		newSize = newSize == 0 ? 1 : 2 * newSize;
		VectorIterator newBegin = calloc(newSize, sizeof(int));
		VectorIterator newEnd = copy(vector, vector, newBegin, oldBegin, _position);
		construct(newEnd, _value);
		vectorIteratorIncreasePrefix(&newEnd);
		newEnd = copy(vector, vector, newEnd, _position, oldEnd);
		destructIn(Vector, oldBegin, oldEnd);
		free(oldBegin);
		_this->begin_ = newBegin;
		_this->end_ = newEnd;
		_this->endOfStorage_ = vectorIteratorAdd(&newBegin, newSize);
	}
	VectorIterator newBegin = vectorBegin(_this);
	return vectorIteratorAdd(&newBegin, diff);
}

VectorIterator vectorInsertN(Vector *_this, VectorIterator _position, size_t _n, int _value) {
	VectorIterator oldBegin = vectorBegin(_this);
	VectorIterator oldEnd = vectorEnd(_this);
	VectorIterator oldEndOfStorage = _this->endOfStorage_;
	ptrdiff_t diff = vectorIteratorDiff(&_position, &oldBegin);
	if ((size_t) vectorIteratorDiff(&oldEndOfStorage, &oldEnd) >= _n) {
		VectorIterator newEnd = vectorIteratorAdd(&oldEnd, _n);
		VectorIterator vectorIterator = copyBackward(vector, vector, newEnd, _position, oldEnd);
		for (; vectorIteratorNotEqualTo(&_position, &vectorIterator); vectorIteratorIncreasePrefix(&_position)) {
			*vectorIteratorIndirect(&_position) = _value;
		}
		_this->end_ = newEnd;
	}
	else {
		size_t newSize = vectorSize(_this);
		newSize = newSize + max(newSize, _n);
		VectorIterator newBegin = calloc(newSize, sizeof(int));
		VectorIterator newEnd = copy(vector, vector, newBegin, oldBegin, _position);
		for (VectorIterator vectorIterator = vectorIteratorAdd(&newEnd, _n); vectorIteratorNotEqualTo(&newEnd, &vectorIterator);) {
			construct(newEnd, _value);
			vectorIteratorIncreasePrefix(&newEnd);
		}
		newEnd = copy(vector, vector, newEnd, _position, oldEnd);
		destructIn(Vector, oldBegin, oldEnd);
		free(oldBegin);
		_this->begin_ = newBegin;
		_this->end_ = newEnd;
		_this->endOfStorage_ = vectorIteratorAdd(&newBegin, newSize);
	}
	VectorIterator newBegin = vectorBegin(_this);
	return vectorIteratorAdd(&newBegin, diff);
}

VectorIterator vectorInsertIn(Vector *_this, VectorIterator _position, VectorIterator _first, VectorIterator _last) {
	VectorIterator oldBegin = vectorBegin(_this);
	VectorIterator oldEnd = vectorEnd(_this);
	VectorIterator oldEndOfStorage = _this->endOfStorage_;
	ptrdiff_t diff = vectorIteratorDiff(&_position, &oldBegin);
	size_t n = (size_t) vectorIteratorDiff(&_last, &_first);
	if ((size_t) vectorIteratorDiff(&oldEndOfStorage, &oldEnd) >= n) {
		VectorIterator newEnd = vectorIteratorAdd(&oldEnd, n);
		copyBackward(vector, vector, newEnd, _position, oldEnd);
		copy(vector, vector, _position, _first, _last);
		_this->end_ = newEnd;
	}
	else {
		size_t newSize = vectorSize(_this);
		newSize = newSize + max(newSize, n);
		VectorIterator newBegin = calloc(newSize, sizeof(int));
		VectorIterator newEnd = copy(vector, vector, newBegin, oldBegin, _position);
		newEnd = copy(vector, vector, newEnd, _first, _last);
		newEnd = copy(vector, vector, newEnd, _position, oldEnd);
		destructIn(Vector, oldBegin, oldEnd);
		free(oldBegin);
		_this->begin_ = newBegin;
		_this->end_ = newEnd;
		_this->endOfStorage_ = vectorIteratorAdd(&newBegin, newSize);
	}
	VectorIterator newBegin = vectorBegin(_this);
	return vectorIteratorAdd(&newBegin, diff);
}

void vectorErase(Vector *_this, VectorIterator _position) {
	vectorEraseN(_this, _position, 1);
}

void vectorEraseN(Vector *_this, VectorIterator _position, size_t _n) {
	vectorEraseIn(_this, _position, vectorIteratorAdd(&_position, _n));
}

void vectorEraseIn(Vector *_this, VectorIterator _first, VectorIterator _last) {
	VectorIterator oldEnd = vectorEnd(_this);
	_this->end_ = copy(vector, vector, _first, _last, oldEnd);
	destructIn(Vector, vectorEnd(_this), oldEnd);
}

bool vectorEmpty(const Vector *_this) {
	VectorConstIterator begin = vectorBeginConst(_this);
	VectorConstIterator end = vectorEndConst(_this);
	return vectorIteratorEqualTo((VectorIterator const *) &begin, (VectorIterator const *) &end);
}

size_t vectorCapacity(const Vector *_this) {
	VectorConstIterator begin = vectorBeginConst(_this);
	VectorConstIterator endOfStorage = _this->endOfStorage_;
	return (size_t) vectorIteratorDiff((VectorIterator const *) &endOfStorage, (VectorIterator const *) &begin);
}

size_t vectorSize(const Vector *_this) {
	VectorConstIterator begin = vectorBeginConst(_this);
	VectorConstIterator end = vectorEndConst(_this);
	return (size_t) vectorIteratorDiff((VectorIterator const *) &end, (VectorIterator const *) &begin);
}

void vectorClear(Vector *_this) {
	vectorEraseIn(_this, vectorBegin(_this), vectorEnd(_this));
}

void vectorResize(Vector *_this, size_t _n) {
	VectorIterator begin = vectorBegin(_this);
	size_t oldSize = vectorSize(_this);
	if (_n < oldSize) {
		vectorEraseIn(_this, vectorIteratorAdd(&begin, _n), vectorEnd(_this));
	}
	else {
		vectorInsertN(_this, vectorEnd(_this), _n - oldSize, 0);
	}
}

void vectorSort(VectorIterator _first, VectorIterator _last) {
	VectorIterator center = center(Vector, _first, _last);
	if (vectorIteratorEqualTo(&center, &_first)) {
		return;
	}
	VectorIterator front = _first;
	VectorIterator back = vectorIteratorSubtract(&_last, 1);
	int pivot = median(*vectorIteratorIndirect(&front), *vectorIteratorIndirect(&center), *vectorIteratorIndirect(&back));
	do {
		if (*vectorIteratorIndirect(&front) > pivot) {
			while (*vectorIteratorIndirect(&back) > pivot) {
				vectorIteratorDecreasePrefix(&back);
				if (vectorIteratorEqualTo(&front, &back)) {
					vectorSort(_first, front);
					vectorSort(front, _last);
					return;
				}
			}
			swap(vectorIteratorIndirect(&front), vectorIteratorIndirect(&back));
		}
		vectorIteratorIncreasePrefix(&front);
	} while (vectorIteratorLessThan(&front, &back));
	vectorSort(_first, front);
	vectorSort(front, _last);
}
